/*
 * @lc app=leetcode.cn id=204 lang=typescript
 *
 * [204] 计数质数
 */

// @lc code=start
function countPrimes(n: number): number {
  // 标记素数1，合数0
  const isPrimes = new Array(n).fill(1);
  // 记录每一个素数
  const primes = [];
  for (let i = 2; i < n; i++) {
    if (isPrimes[i]) primes.push(i);
    for (let j = 0; j < n && i * primes[j] < n; j++) {
      isPrimes[i * primes[j]] = 0;
      // 保证每个合数被标记一次
      if (i % primes[j] === 0) break;
    }
  }

  return primes.length;
}
// @lc code=end
